package com.leetcode.p100;

import com.utils.DataUtils;

import java.util.List;

public class Test120 {

    private int min = Integer.MAX_VALUE;

    public int minimumTotal(List<List<Integer>> triangle) {
        help(triangle, 1);
        return min;
    }

    private void help(List<List<Integer>> triangle, int level) {
        if (level == triangle.size()) {
            List<Integer> last = triangle.get(level - 1);
            for (Integer temp : last) {
                min = Math.min(min, temp);
            }
            return;
        }

        List<Integer> preList = triangle.get(level - 1);

        int size = triangle.get(level).size();
        for (int i = 0; i < size; i++) {
            int current = triangle.get(level).get(i);
            if (i == 0) {
                triangle.get(level).set(i, current + preList.get(i));
            } else {
                if (i == size - 1) {
                    triangle.get(level).set(i, current + preList.get(i - 1));
                } else {
                    triangle.get(level).set(i, current + Math.min(preList.get(i - 1), preList.get(i)));
                }
            }
        }
        help(triangle, level + 1);
    }

    public static void main(String[] args) {
        Test120 test = new Test120();

        List<List<Integer>> triangle = DataUtils.string2ListListInteger("[[2],[3,4],[6,5,7],[4,1,8,3]]");

        int result = test.minimumTotal(triangle);

        System.out.println(result);

    }

}
